package 动态规划;

import java.util.Set;

public class NC_拆分字符串 {
    //注意边界值问题，因为在字符串中存储是从0下标开始，而在数组中实际是从1开始、arr[0]为辅助--用来判断
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] canBreak = new boolean[s.length() + 1];
        // 初始化F(0)=true
        canBreak[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            // true{j < i && F(j) && substr[j+1,i]能在词典中找到}
            for (int j = 0; j < i; j++) {
                // F(j): 之前的字符串已经确定了可以有从集合中找到分割串的结果为true
                // 如果从[j+1, i]这个子串也在集合中，那么相对的 F(i) 就找到了结果，为true
                if (canBreak[j] && dict.contains(s.substring(j, i))) { //substring左闭右开且字符向前挪一个
                    // 通过前面已知的 F(j) 从小到大来求 F(i)
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }
}
